#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:

    int reversePairs(vector<int>& record) {
        int n = record.size();
        vector<int>v(n);
        return    msort(record, 0, n - 1, v);

    }
    int  msort(vector<int>& record, int left, int right, vector<int>& v)
    {
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
        ret += msort(record, left, mid, v);
        ret += msort(record, mid + 1, right, v);
        int begin1 = left, begin2 = mid + 1;
        int i = begin1;
        while (begin1 <= mid && begin2 <= right)
        {
            if (record[begin1] <= record[begin2]) v[i++] = record[begin1++];
            else
            {
                ret += mid - begin1 + 1;
                v[i++] = record[begin2++];
            }
        }
        while (begin1 <= mid)
        {
            v[i++] = record[begin1++];
        }
        while (begin2 <= right)
        {
            v[i++] = record[begin2++];
        }
        for (int j = left; j < i; j++)
        {
            record[j] = v[j];
        }
        return ret;
    }
};